﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0169_LongestPalindrome : IAlgorithm
    {
        // 409. 最长回文串

        // 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
        // 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

        // 提示:
        //  1 <= s.length <= 2000
        //  s 只由小写 和/或 大写英文字母组成

        public void Test()
        {
            // 算法参数定义
            var s = "abccccdd";
            // 算法执行与打印
            Console.WriteLine(LongestPalindrome(s));
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public int LongestPalindrome(string s)
        {
            var hashSet = new HashSet<char>();
            var doubleCount = 0;
            foreach (var c in s)
                if (hashSet.Contains(c))
                {
                    doubleCount++;
                    hashSet.Remove(c);
                }
                else
                {
                    hashSet.Add(c);
                }

            return doubleCount * 2 + (hashSet.Count > 0 ? 1 : 0);
        }
    }
}
